package leetcode.day_2021_04_12_2021_04_18;

import java.util.*;

/**
 * 90. 子集 II
 * https://leetcode-cn.com/problems/subsets-ii/
 */
public class LeetCode0090 {
    public static List<List<Integer>> subsetsWithDup(int[] nums) {
        int length = nums.length;
        if (length == 0) {
            return null;
        }
        List<List<Integer>> result = new ArrayList<>();
        Set<String> set = new HashSet<>();
        List<Integer> nullList = new ArrayList<>();
        result.add(nullList);
        set.add(nullList.toString());
        for (int i=0; i<length; i++) {
            for (int j=result.size()-1; j>=0; j--) {
                List<Integer> list = new ArrayList<>(result.get(j));
                list.add(nums[i]);
                if (!set.contains(list.toString())) {
                    result.add(list);
                    Collections.sort(list);
                    set.add(list.toString());
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 2};
        System.out.println(subsetsWithDup(nums).toString());
    }
}
